# -*- coding: utf-8 -*-

from random import choice

def bubble(li):
    """冒泡排序：
    1）将一个位置的冒泡单独拎出来，比如轮到5号位冒泡，那么意味着冒到4号位之后，只需要比较4~5号位大小
    2）每个位置冒结束之后，数组状态都有变化，所以从尾部向前每个位置都需要按顺序冒泡"""
    
    def maopao(n):
        if n==0:
            return
        maopao(n-1)
        if li[n-1] > li[n]:
            li[n-1], li[n] = li[n], li[n-1]
    
    s = len(li)
    for i in [s-1-n for n in range(0, s)]:
        maopao(i)


def insert(li):
    """插入排序：
    1）轮到对i位置上的数进行排序时，假设前面i-1位都已经排好，只需要将第i位插入到有序区间
    2）实际上也可以直接使用循环"""
    # for i in range(len(li)):
    #     for p in range(i+1):
    #         if li[p] > li[i]:
    #             break
    #     t = li[i]
        
    #     move = list(range(p, i))
    #     move.reverse()
    #     for c in move:
    #         li[c+1] = li[c]
    #     li[p] = t
    # print(li)

    def charu(i):
        if i == 0:
            return
        charu(i-1)

        for p in range(i+1):
            if li[p] > li[i]:
                break
        t = li[i]
        
        move = list(range(p, i))
        move.reverse()
        for c in move:
            li[c+1] = li[c]
        li[p] = t
    
    charu(len(li)-1)


def select(li):
    """选择排序：
    1）当为第i为选择合适数字时，前面区间为从小到大的有序区间，需要从第i位后的无须区间内选择最小的数，放到第i位"""
    
    s = len(li)
    def xuanze(i):
        if i < 0:
            return
        xuanze(i-1)

        _min, _addr = li[i], i
        for p in range(i, s):
            if li[p] < _min:
                _min = li[p]
                _addr = p
                
        li[i], li[_addr] = li[_addr], li[i]
    
    xuanze(len(li)-1)


def merge(li):
    """归并排序"""
    def hebing(left, right):
        st = []
        pl, pr = 0, 0
        sl, sr = len(left), len(right)
        while True:
            if pl == sl:
                for p in range(pr, sr):
                    st.append(right[p])
                break
            
            elif pr == sr:
                for p in range(pl, sl):
                    st.append(left[p])
                break

            elif left[pl] < right[pr]:
                st.append(left[pl])
                pl += 1
            else:
                st.append(right[pr])
                pr += 1
        return st

    def guibing(li):
        s = len(li)
        if s == 1:
            return li
        left, right = li[0:s//2], li[s//2:]
        left = guibing(left)
        right = guibing(right)
        return hebing(left, right)
    
    return guibing(li)

def quick(li):
    """快速排序"""

    def kuaisu(li):
        if len(li) <= 1:
            return li

        pivot = choice(li)
        small, pivotl, large = [], [], []
        for n in li:
            if n < pivot:
                small.append(n)
            elif n > pivot:
                large.append(n)
            else:
                pivotl.append(n)
        
        smalll = kuaisu(small)
        largel = kuaisu(large)

        return smalll+pivotl+largel
    
    return kuaisu(li)


def bucket(li):
    """桶排序：
    高考成绩排名，分数区间[0: 750]， 形成751个桶，桶与桶之间天然有序，桶内可以不用排序"""
    return


if __name__ == '__main__':
    lia, lib, lic, libd, libe = [2,5,9,4,19,3,7,2], [5,6,7,2,9,4,1,8,5,0,7], [3,8,4,6,9,7,1,0,5,2,4,11], [9,8,7,5,8,2,6,45,89,128,56,97,100,74,61,85,28,97,66], [1,2,5,6,8,7,1,9,58,16,74,85,29,67,81,106,-8,75,0,5,3,98,77,100]
    bubble(lia)
    print(lia)

    insert(lib)
    print(lib)

    select(lic)
    print(lic)

    libd = merge(libd)
    print(libd)

    libe = quick(libe)
    print(libe)

